package sortAlgorithm;

import java.util.PriorityQueue;

//一下代码均在leetcode上测试通过，在如下链接题目有一部分会超时，但超时不是代码有bug
//https://leetcode.cn/problems/sort-an-array/
// 以下都是  从小 -> 大
public class Rank {
    private static void swap(int[] arr,int i,int j){
        int tep = arr[i];
        arr[i] = arr[j];
        arr[j] = tep;
    }

    //1.冒泡排序
    /*
    * 冒泡排序：像在海里的气泡一样，最底下的最小，越往上越大
    * 在这里我们比较前后两数字（也可以说是前后两个气泡），大的在后，小的在前，不对的我们交换一下
    * */
    public static void bubbleSort(int[] arr){
         int n = arr.length;
         for(int i = 0;i < n;i++){//比较的趟数
             boolean check = true;
             for (int j = 1;j < n - i;j++){//这里每次固定无序数中的一个最大的数
                 if(arr[j] < arr[j-1]){
                     check = false;
                     swap(arr,j-1,j);
                 }
             }
             if(check){//如果check == true 说明数组已经有序！
                 break;
             }
         }
    }

    //2.插入排序
    /* 改进
     * 插入排序是在有序数组中，再插入一个
    * */
    public static void insertionSorting(int[] arr){
        int n = arr.length;
        for (int count = 1; count < n; count++) {
            int target = arr[count];//要插入的数字
            int i = count-1;
            for ( ;i >= 0; i--) {
                if(arr[i] > target){
                    arr[i+1] = arr[i];
                }else {
                    break;
                }
            }
            arr[i+1] = target;
        }
    }

    public static void insertionSorting1(int[] arr){
        int n = arr.length;
        for (int count = 0; count < n; count++) {//插入的次数
            int target = arr[count];//要插入的数字
            int i = 0;
            for(;i < count;i++){//选择插入位置
                if(arr[i] > target){
                    break;
                }
            }
            // 注意： 是从后 往 前，而不是从前 往 后
            for (int j = count; j > i; j--) {//将[i,count-1]区间数字统一向后移动一位，空出i位置
                arr[j] = arr[j-1];
            }
            arr[i] = target;
        }
    }

    //3.选择排序
    /*
    * 选择排序：直接从一堆无序数中选择出一个最大或最小的，拍放在他应该放到位置上
    * 如下：我们选择最小的
    * */
    public static void selectionSort(int[] arr){
        int n = arr.length;
        for (int i = 0; i < n; i++) {//选择的次数
            int maxIndex = i;
            int maxData = arr[i];
            for (int j = i+1; j < n; j++) {//选择区间[i,n-1]
                if(maxData > arr[j]){
                    maxData = arr[j];
                    maxIndex = j;
                }
            }
            swap(arr,i,maxIndex);
        }
    }

    //4.希尔排序
    /*
    * 核心：分组，组内进行插入排序，逐渐减少组数。
    * 值得注意的是到现在为止人们还未找到，如何分组效率最高。
    * */
    //改进
    public static void shellSort(int[] arr){
        int n = arr.length;
        for (int gap = n/2; gap > 0; gap = gap/2) {  //gap 表示间隔数
            groupInsertionSort(arr,gap,n);//进行插入排序
        }
    }

    private static void groupInsertionSort(int[] arr,int gap,int n) {
        for (int i = gap; i < n; i++) {//这里表示插入次数
            int target = arr[i];//要插入的数字
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if(arr[j] > target){
                    arr[j + gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = target;
        }
    }

    public static void shellSort1(int[] arr){
        int n = arr.length;
        for (int gap = n; gap > 0; gap = gap/2) {  //gap 表示间隔数
            for (int i = 0; i < gap; i++) {//进行分组, 其中组数 等于 gap
                groupInsertionSort1(arr,gap,n);//进行组内插入排序
            }
        }
    }

    private static void groupInsertionSort1(int[] arr,int gap,int n) {
        for (int i = 0; i < n; i += gap) {//这里表示插入次数
            int target = arr[i];//要插入的数字
            int j = 0;
            for ( ;j < i; j+=gap) {//选择插入位置
                if(arr[j] > target){
                    break;
                }
            }
            for (int k = i; k > j; k -= gap) {//将数字统一向后移动一间隔，空出j位置
                arr[k] = arr[k - gap];
            }
            arr[j] = target;
        }
    }

    //5.堆排序
    /*
    *1.最简单的就是使用内置函数  priorityQueue（小根推）
    * 如果使用内置函数，那可就太没意思了
     */
    public static void heapSort1(int[] arr){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            priorityQueue.add(arr[i]);
        }
        int i = 0;
        while (!priorityQueue.isEmpty()){
            arr[i++] = priorityQueue.poll();
        }
    }

    public static void heapSort(int[] arr){

    }

    //6.归并排序


    //7.快速排序
    /*
    * 基本原理是分治和递归。它的基本思路是，在数组中选择一个元素作为基准值，
    * 然后将数组中小于基准值的元素移动到它的左边，大于基准值的元素移动到它的右边。然后重复如上操作。
    * */
    public static void quickSort(int[] arr) {
        qSort1(arr,0,arr.length-1);
    }
    //1.挖坑法（在特殊情况下会达到O(n2),原因标准数选择的不好）
    private static void qSort1(int[] arr, int left, int right) {
        if (left >= right)return;//出口
        //这里采用三数取中(这只能提升一点效率，也就是经可能的选的中位数)
        // int standardI = findStandardI(arr, left, right);
        // int standard = arr[standardI];
        // swap(arr, standardI, left);
        // standardI = left;
        //这里指定最右边，效率会低下。
        int standardI = left;
        int standard = arr[left];

        for (int l = left, r = right; l < r;) {
            while (l < r && arr[r] >= standard) {
                r--;
            }
            arr[standardI] = arr[r];
            standardI = r;
            while (l < r && arr[l] <= standard) {
                l++;
            }
            arr[standardI] = arr[l];
            standardI = l;
        }

        arr[standardI] = standard;

        qSort1(arr, left, standardI-1);
        qSort1(arr, standardI + 1, right);
    }


    private static int findStandardI(int[] arr, int left, int right) {
        int mid = left + (right - left) / 2;//这种写法可以避免越界
        if(arr[left] < arr[mid]){
            if(arr[mid] <= arr[right]){
                return mid;
            }
            if(arr[right] >= arr[left]){
                return right;
            }
            if(arr[left] >= arr[right]){
                return left;
            }
        }else {
            if(arr[right] >= arr[left]){
                return left;
            }
            if(arr[mid] >= arr[right]){
                return mid;
            }
            if(arr[right] >= arr[mid]){
                return right;
            }
        }
        return -1;//执行到这个说明上面逻辑有问题
    }




    // 其他排序
    //8.计数排序


    //9.基数排序



    //10.桶排序
    /*
    *力扣链接：https://leetcode.cn/problems/top-k-frequent-elements/  347题
    * 这题还有其他更优解，但也可用桶排序
     */

}
